package LimitedTimeGame.Day_0217;

/**
 * @author zxc
 * @date 2023/02/17 17:17
 **/

import java.util.LinkedList;
import java.util.Queue;

/**
 * 题目 ：分割链表
 * 题目详述 ：
 * 给你一个链表的头节点 head 和一个特定值 x ，
 * 请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 提示：
 * 链表中节点的数目在范围 [0, 200] 内
 * -100 <= Node.val <= 100
 * -200 <= x <= 200
 *
 */
public class Partition {
    /**
     * 思路 ：
     * ===》
     * 即，利用队列 "先进先出"的特性，
     * （1）使用queue1队列存储 所有小于x的链表节点;
     * （2）同时，使用queue2队列存储 所有大于等于x的链表节点;
     * （3）构建新链表，逐步遍历queue1 && queue2中的所有链表节点; 同时，将其中的链表节点进行相连;
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        Queue<ListNode> queue1 = new LinkedList<>();
        Queue<ListNode> queue2 = new LinkedList<>();
        while(head != null){
            if(head.val < x){
                queue1.add(head);
            }
            else {
                queue2.add(head);
            }
            ListNode temp = head;
            head = head.next;
            temp.next = null;
        }
        // 虚拟头结点 ：
        ListNode dummy = new ListNode();
        ListNode node = dummy;
        while(!queue1.isEmpty()){
            // 首先，指定node节点的next节点;
            // 再使得node节点 == queue1.poll;
            node.next = queue1.isEmpty() ? null : queue1.peek();
            node = queue1.poll();
        }
        while(!queue2.isEmpty()){
            node.next = queue2.peek();
            node = queue2.poll();
            node.next = queue2.isEmpty() ? null : queue2.peek();
        }
        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {};
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
